import java.util.stream.IntStream;

public class Sort {
    public static void main(String[] args) {
//        int[] bubble = new int[]{9, 4, 8, 66, 1, 2, 3, 8, 4, 845};
//        IntStream.of(bubbleSort(bubble)).forEach(System.out::println);

        int[] quick = new int[]{9,5,31,67,57,100,91,1,65,88};
        IntStream.of(quickSort(quick, 0, 9)).forEach(System.out::println);
    }

    /**
     * 快速排序
     * @param numbers 数组
     * @param low 第一位下标
     * @param high 最后一位下标
     * @return 排序后的数组
     */
    public static int[] quickSort(int[] numbers, int low, int high) {
        if (low >= high) {
            return numbers;
        }

        int left=low;
        int right = high;
        int mk = numbers[low];//以第一个数位基数

        while (left < right) {
            while (left < right && numbers[right] >= mk) {
                right--;
            }
            numbers[left] = numbers[right];//把小于基数的放左边
            while (left < right && numbers[left] <= mk) {
                left++;
            }
            numbers[right] = numbers[left];//把大于基数的放右边
        }
        numbers[left] = mk;
        quickSort(numbers, low, left - 1);
        quickSort(numbers, right + 1, high);
        return numbers;
    }

    /**
     * 冒泡排序
     * @param numbers 数组
     * @return 排序后的数组
     */
    public static int[] bubbleSort(int[] numbers) {
        int temp;
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length - i - 1; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        return numbers;
    }
}
